'''
距离计算
文件读写操作
其他通用功能
'''
import math
import os
import random
import sys

import Globals
import copy


# 保存解决方案的路线到指定文件
def save_routes_to_file(chromosome, file_path):
    with open(file_path, 'w') as file:
        for route_index, route in enumerate(chromosome.routes, start=1):
            # 格式化路线信息
            route_info = f"Route {route_index}: {' -> '.join(map(str, route.customers))}\n"
            # distance_info = f"Total Distance: {route.travel_dist:.2f} units\n"
            # time_info = f"Total Time: {route.travel_time:.2f} units\n"

            # 将路线信息写入文件
            file.write(route_info)
            # file.write(distance_info)
            # file.write(time_info)
            file.write("\n")  # 添加一个空行作为路线间的分隔符

        # print(f"Routes have been successfully saved to {file_path}")


# 从文件名获取数据
def get_data(distance_file, time_file, spec_file):
    c_num = Globals.customer_num
    # 初始化peerTime, peerDistance, 和customer列表
    Globals.peer_time = [[0.0 for _ in range(c_num + 2)] for _ in range(c_num + 2)]
    Globals.peer_distance = [[0.0 for _ in range(c_num + 2)] for _ in range(c_num + 2)]
    Globals.customer = [Globals.Customer() for _ in range(c_num + 2)]
    Globals.max_delay_time = [1800 for _ in range(c_num + 2)]

    # 读取规格文件
    with open(spec_file, 'r') as f_spec:
        # 跳过文件的前四行
        for _ in range(4): next(f_spec)
        # 读取最大容量值
        specLine = f_spec.readline().strip().split()
        Globals.vehicle_num = int(specLine[0])
        Globals.max_capacity = float(specLine[1])

        # 再次跳过四行
        for _ in range(4): next(f_spec)
        # 读取客户信息
        for i in range(c_num + 1):
            data = f_spec.readline().split()
            Globals.customer[i].id = int(data[0])
            Globals.customer[i].x = float(data[1])
            Globals.customer[i].y = float(data[2])
            Globals.customer[i].delivery_demand = float(data[3])
            Globals.customer[i].pick_up_demand = float(data[4])
            Globals.customer[i].begin_time = float(data[5])
            Globals.customer[i].end_time = float(data[6])
            Globals.customer[i].server_time = float(data[7])
    Globals.customer[c_num + 1] = Globals.customer[0]

    # 打印测试数据
    # for i in range(len(Globals.customer)):
    #     print(
    #         "ID: {}, X: {}, Y: {}, Delivery Demand: {}, Pick-up Demand: {}, Start Time: {}, "
    #         "End Time: {}, Service Time: {}".format(
    #             Globals.customer[i].id, Globals.customer[i].x, Globals.customer[i].y,
    #             Globals.customer[i].delivery_demand, Globals.customer[i].pick_up_demand,
    #             Globals.customer[i].begin_time, Globals.customer[i].end_time, Globals.customer[i].server_time))

    # 读取时间文件和距离文件
    with open(time_file, 'r') as f_time, open(distance_file, 'r') as f_distance:
        for i in range(c_num + 1):
            # 读取一行数据并按空格分割
            time_line = f_time.readline().strip().split()
            for j in range(len(time_line)):
                Globals.peer_time[i][j] = float(time_line[j])
            # 将字符串列表转换为浮点数列表，并赋值给 peerTime 的第 i 行
            distance_line = f_distance.readline().strip().split()
            for j in range(len(distance_line)):
                Globals.peer_distance[i][j] = float(distance_line[j])

    # 处理特殊情况
    # 即将配送中心到客户i的距离设置为客户i到配送中心，即终点的距离
    for i in range(c_num + 2):
        Globals.peer_time[i][c_num + 1] = Globals.peer_time[i][0]
        Globals.peer_distance[i][c_num + 1] = Globals.peer_distance[i][0]
        Globals.peer_time[c_num + 1][i] = Globals.peer_time[0][i]
        Globals.peer_distance[c_num + 1][i] = Globals.peer_distance[0][i]

    # 打印测试数据
    # print("Peer Time Matrix:")
    # for i in range(c_num + 2):  # 假设包括了配送中心作为起点和终点
    #     for j in range(c_num + 2):
    #         print(f"{Globals.peer_time[i][j]:.2f}", end=' ')
    #     print()  # 新的一行开始前打印一个换行符
    #
    # print("\nPeer Distance Matrix:")
    # for i in range(c_num + 2):
    #     for j in range(c_num + 2):
    #         print(f"{Globals.peer_distance[i][j]:.2f}", end=' ')
    #     print()  # 新的一行开始前打印一个换行符


def get_distance(route):
    # 计算总送货量和取货量
    size = len(route.customers)
    route.delivery_capacity = 0
    route.pick_up_capacity = 0
    for i in range(1, size - 1):
        cust = route.customers[i]
        route.delivery_capacity += Globals.customer[cust].delivery_demand
        route.pick_up_capacity += Globals.customer[cust].pick_up_demand

    # 初始化路线的总行驶距离为0
    route.travel_dist = 0

    # 计算总行驶距离并重置a_distance和b_distance
    for i in range(len(route.customers) - 1):
        cur_cust = route.customers[i]
        next_cust = route.customers[i + 1]
        route.travel_dist += Globals.peer_distance[cur_cust][next_cust]
        Globals.a_distance[cur_cust] = 0
        Globals.b_distance[cur_cust] = 0

    # 计算从路线起点到每个客户点的累计距离
    Globals.b_distance[route.customers[0]] = 0
    for i in range(1, len(route.customers) - 1):
        pre_cust = route.customers[i]
        cur_cust = route.customers[i]
        Globals.b_distance[cur_cust] = (
                Globals.b_distance[pre_cust] + Globals.peer_distance[pre_cust][cur_cust]
        )

    # 计算从每个客户点到路线终点的累计距离
    for i in range(len(route.customers) - 2, 0, -1):
        cur_cust = route.customers[i]
        next_cust = route.customers[i + 1]
        Globals.a_distance[cur_cust] = (
                Globals.a_distance[next_cust] + Globals.peer_distance[cur_cust][next_cust]
        )


def get_time(route):
    # 初始化变量
    route.travel_time = 0
    route.delay_time = 0
    route.wait_time = 0
    Globals.total_wait[0] = 0
    Globals.total_delay[0] = 0
    # 遍历所有客户
    for i in range(len(route.customers) - 1):

        cur_cust = route.customers[i]
        next_cust = route.customers[i + 1]

        wait = delay = 0
        # 旅行时间
        route.travel_time += Globals.peer_time[cur_cust][next_cust]
        # 到达客户时间
        Globals.a_time[next_cust] = route.travel_time

        # 如果到达下一个客户的时间超过了该客户的最晚服务时间
        # 则将超出的时间视为延误，累加到route.delay_time并更新total_delay数组
        if route.travel_time > Globals.customer[next_cust].end_time:
            delay = route.travel_time - Globals.customer[next_cust].end_time
        route.delay_time += delay
        Globals.total_delay[next_cust] = Globals.total_delay[cur_cust] + delay

        # 如果到达时间早于客户的最早服务时间
        # 则需要等待，等待时间累加到route.wait_time并更新w_time和total_wait数组
        if route.travel_time < Globals.customer[next_cust].begin_time:
            wait = Globals.customer[next_cust].begin_time - route.travel_time
        Globals.w_time[next_cust] = wait
        Globals.total_wait[next_cust] = Globals.total_wait[next_cust] + wait
        route.wait_time += wait

        # 对于每个客户，行驶时间需要加上在该客户处的等待时间和服务时间(s_time)
        route.travel_time += (wait + Globals.customer[next_cust].server_time)
        Globals.l_time[next_cust] = route.travel_time

    # 初始化起点的离开时间和最大等待时间
    Globals.l_time[route.customers[0]] = 0
    Globals.max_wait[route.customers[0]] = Globals.customer[route.customers[0]].end_time - Globals.a_time[
        route.customers[0]]

    # 从路线的倒数第二个客户开始向起点方向更新max_wait
    for i in range(len(route.customers) - 2, 0, -1):
        current_customer = route.customers[i]
        next_customer = route.customers[i + 1]
        # 更新max_wait为当前客户的最晚服务时间加上允许的最大延误减去到达当前客户的累计时间
        # 和下一个客户的max_wait加上当前客户的等待时间的较小值
        Globals.max_wait[current_customer] = min(
            # 客户的最晚服务时间加上允许的最大延误减去到达该客户的实际时间
            Globals.customer[current_customer].end_time + Globals.max_delay_time[current_customer] - Globals.a_time[
                current_customer],
            # 下一个客户的 max_wait 加上当前客户的等待时间
            Globals.w_time[current_customer] + Globals.max_wait[next_customer]
        )

    # 重置起点的总等待时间和总延误时间为0
    Globals.total_wait[route.customers[0]] = 0
    Globals.total_delay[route.customers[0]] = 0


# 为染色体计算多个目标函数的值
def get_f(chromosome):
    # 初始化目标函数值
    chromosome.f = [0] * Globals.FUNC_NUM
    # 目标函数1：路线（车辆）数量
    chromosome.f[0] = len(chromosome.routes)
    # 目标函数2：总行驶距离
    chromosome.f[1] = sum(route.travel_dist for route in chromosome.routes)
    # 目标函数3：最长行驶时间
    # t_time = 0
    # r = None
    # for route in chromosome.routes:
    #     if route.travel_time > t_time:
    #         t_time = route.travel_time
    #         r = route
    # print(t_time,r.customers)
    chromosome.f[2] = max(route.travel_time for route in chromosome.routes) if chromosome.routes else 0
    # 目标函数4：总等待时间
    chromosome.f[3] = sum(route.wait_time for route in chromosome.routes)
    # 目标函数5：总延误时间
    chromosome.f[4] = sum(route.delay_time for route in chromosome.routes)


def get_capacity(route, index):
    route.d_capacity = 0
    route.p_capacity = 0
    size = len(route.customers)

    for i in range(size):
        Globals.pi_plus[index][i] = 0
        Globals.pi_minus[index][i] = 0
        Globals.delta_plus[index][i] = 0
        Globals.delta_minus[index][i] = 0

    for i in range(size):
        cust = route.customers[i]
        Globals.pi_minus[index][size - 1] += Globals.customer[cust].pick_up_demand
        Globals.delta_plus[index][0] += Globals.customer[cust].delivery_demand
    Globals.delta_minus[index][0] = Globals.delta_plus[index][0]

    for i in range(1, size):
        pre_cust = route.customers[i - 1]
        Globals.pi_minus[index][i] = Globals.pi_minus[index][i - 1] + Globals.customer[pre_cust].pick_up_demand
        Globals.delta_minus[index][i] = Globals.delta_minus[index][i - 1] - Globals.customer[pre_cust].delivery_demand

    Globals.pi_plus[index][0] = Globals.customer[route.customers[0]].pick_up_demand
    Globals.delta_plus[index][0] -= Globals.customer[route.customers[0]].delivery_demand

    for i in range(1, size - 1):
        cust = route.customers[i]
        Globals.pi_plus[index][i] = Globals.pi_plus[index][i - 1] + Globals.customer[cust].pick_up_demand
        Globals.delta_plus[index][i] = Globals.delta_plus[index][i - 1] - Globals.customer[cust].delivery_demand

    Globals.M_minus[index][1] = Globals.pi_minus[index][1] + Globals.delta_minus[index][1]
    for i in range(2, size):
        Globals.M_minus[index][i] = max(Globals.M_minus[index][i - 1],
                                        Globals.pi_minus[index][i] + Globals.delta_minus[index][i])

    Globals.M_plus[index][size - 2] = Globals.pi_plus[index][size - 2] + Globals.delta_plus[index][size - 2]
    for i in range(size - 3, -1, -1):
        Globals.M_plus[index][i] = max(Globals.M_plus[index][i + 1],
                                       Globals.pi_plus[index][i] + Globals.delta_plus[index][i])


def get_wf(chromosome, r_lambda):
    sum = 0
    for i in range(Globals.FUNC_NUM):
        max_num = Globals.max_num[i]
        min_num = Globals.min_num[i]
        # 原版解决方案会出现分母为0的情况
        # sum += r_lambda[i] * (chromosome.f[i] - min_num) / (max_num - min_num - 1)

        # 新解决方案，在分母中添加一个非常小的正数（epsilon），以确保不会发生除以0的情况
        epsilon = 1e-6
        sum += r_lambda[i] * (chromosome.f[i] - min_num) / (max_num - min_num + epsilon)
    return sum


# 对染色体的每个目标函数值进行转换，并存储在box_f数组中
def get_box(chrome):
    for i in range(Globals.FUNC_NUM):
        if chrome.f[i] == 0:
            chrome.box_f[i] = 0
        else:
            chrome.box_f[i] = math.log(chrome.f[i]) / math.log(1 + Globals.epsilon)


# def cmp_Euclid(index_1, index_2):
#     return Globals.Euclid[index_1] < Globals.Euclid[index_2]

# 计算第i个染色体解决方案的邻接矩阵
# 对于每个权重向量，计算它与其他所有权重向量的欧几里得距离
def get_neighbor(index):
    # 遍历所有权重向量
    for i in range(Globals.N):
        # 这有一个问题，需不需要忽略掉第i个染色体本身
        Globals.Euclid[i] = 0
        # 计算它与指定权重向量（index为其索引）之间的欧几里得距离
        for j in range(Globals.FUNC_NUM):
            Globals.Euclid[i] += math.pow(Globals.lambda_v[i][j] - Globals.lambda_v[index][j], 2)
        Globals.Euclid[i] = math.sqrt(Globals.Euclid[i])

    ind = list(range(Globals.N))
    # 对欧几里得距离进行排序
    ind.sort(key=lambda x: Globals.Euclid[x])
    # 选择距离最近的T个权重向量作为当前权重向量的邻域
    for i in range(Globals.T):
        Globals.B[index][i] = ind[i]


# 遍历当前种群中所有染色体的目标函数值，为每个目标函数找到其最大值和最小值
def get_max_min():
    # 初始化最大值和最小值数组
    for i in range(Globals.FUNC_NUM):
        Globals.max_num[i] = 0
        Globals.min_num[i] = 999999999
    # 遍历种群并更新最大值和最小值
    # 外层循环遍历种群中的每个染色体
    for i in range(Globals.N):
        # 内层循环遍历每个染色体的每个目标函数
        for j in range(Globals.FUNC_NUM):
            if Globals.chromosome[i].f[j] > Globals.max_num[j]:
                Globals.max_num[j] = Globals.chromosome[i].f[j]
            if Globals.chromosome[i].f[j] < Globals.min_num[j]:
                Globals.min_num[j] = Globals.chromosome[i].f[j]


def get_RP(RP, size):
    for i in range(size):
        RP[i] = i
    for i in range(size):
        r0 = i + random.randint(0, size - 1 - i)
        RP[i], RP[r0] = RP[r0], RP[i]


# 判断车辆数量是否大于给定车辆数
def check_vehicle_num(chromosome):
    if len(chromosome.routes) > Globals.vehicle_num:
        return False
    else:
        return True


# 验证染色体（即一组路线）是否满足特定的约束条件（包括路程和时间）
def check_both(chromosome):
    used = [False] * (Globals.customer_num + 1)  # 初始化标记所有客户未被服务

    # 遍历所有路线
    for route in chromosome.routes:
        d_capacity = 0  # 初始化总送货量
        t_time = 0  # 旅行时间
        w_time = 0  # 等待时间

        # 累加送货量，检查是否超过最大容量
        for i in range(1, len(route.customers) - 1):
            current_cust = route.customers[i]
            d_capacity += Globals.customer[current_cust].delivery_demand
            if d_capacity > Globals.max_capacity:
                # print("delivery capacity false!")
                return False

        # 检查送货后的取货操作是否导致超过最大容量
        for i in range(1, len(route.customers) - 1):
            current_cust = route.customers[i]
            d_capacity = d_capacity - Globals.customer[current_cust].delivery_demand + Globals.customer[
                current_cust].pick_up_demand
            if d_capacity > Globals.max_capacity:
                # print(f"路线:{' -> '.join(map(str, route.customers))}")
                # print("pickup capacity false!", d_capacity)
                return False

        # 计算行驶时间，检查是否违反时间窗约束
        for i in range(len(route.customers) - 1):
            current_cust = route.customers[i]
            next_cust = route.customers[i + 1]
            t_time += Globals.peer_time[current_cust][next_cust]

            if next_cust != 0:
                if t_time > Globals.customer[next_cust].end_time + Globals.max_delay_time[next_cust]:
                    # print(f"路线:{' -> '.join(map(str, route.customers))} 客户：{current_cust}")
                    # print("time window violation!")
                    return False
            else:  # 返回配送中心
                if t_time > Globals.customer[0].end_time:
                    # print(f"路线:{' -> '.join(map(str, route.customers))}")
                    # print("depot end time false!")
                    return False
            if t_time < Globals.customer[next_cust].begin_time:
                w_time = Globals.customer[next_cust].begin_time - t_time
            else:
                w_time = 0
            t_time += w_time + Globals.customer[next_cust].server_time

            used[current_cust] = True  # 标记当前客户已被服务

    # 检查是否所有客户都已被服务
    if sum(used[1:]) != Globals.customer_num:  # 排除配送中心的索引0
        # print("Not all customers are served!")
        return False

    return True


def check_best_pos(cust_index, route, r_lambda, now_dist, now_wait, now_delay, r_num):
    feasible = False
    c_index = 0
    # delta_time = 0
    # delta_dist = 0
    # delta = 0
    total_capacity = 0
    min_delta = 99999999
    get_capacity(route, 0)

    # 检查总容量是否超过限制
    for i in range(1, len(route.customers) - 1):
        cust = route.customers[i]
        total_capacity += Globals.customer[cust].delivery_demand
    total_capacity += Globals.customer[cust_index].delivery_demand
    if total_capacity > Globals.max_capacity:
        # print("超重")
        return [False, 0, 0]

    get_time(route)

    # print(f"route:{route.customers}")

    # 遍历路线中的每个客户位置
    for i in range(1, len(route.customers)):
        pre_cust = route.customers[i - 1]
        cust = route.customers[i]

        # 容量约束
        # 配送中心出发到客户的最大载荷
        if Globals.M_minus[0][i] + Globals.customer[cust_index].delivery_demand > Globals.max_capacity:
            # print("超重1")
            return [False, 0, 0]
        # 离开客户到到达配送中心的最大载荷
        if Globals.M_plus[0][i - 1] + Globals.customer[cust_index].pick_up_demand > Globals.max_capacity:
            # print("超重2")
            return [False, 0, 0]

        # 时间约束
        # 假设用户插入到第i个客户之前
        travel_time = 0
        wait_time = Globals.total_wait[pre_cust]
        delay_time = Globals.total_delay[pre_cust]
        Globals.a_time[cust_index] = Globals.l_time[pre_cust] + Globals.peer_time[pre_cust][cust_index]
        # print(f"到达当前客户{cust_index}的时间：{Globals.a_time[cust_index]}")
        # 到达时间不符合时间窗要求
        if Globals.a_time[cust_index] > Globals.customer[cust_index].end_time + Globals.max_delay_time[cust_index]:
            # print("插入客户到达时间晚于下一个用户的时间窗")
            continue

        #  到达时间早于最早服务时间，则产生等待时间
        if Globals.a_time[cust_index] < Globals.customer[cust_index].begin_time:
            wait_time += Globals.customer[cust_index].begin_time - Globals.a_time[cust_index]
            Globals.a_time[cust_index] = Globals.customer[cust_index].begin_time

        # 到达时间晚于客户最晚服务时间，产生延误时间
        if Globals.a_time[cust_index] > Globals.customer[cust_index].end_time:
            delay_time += Globals.a_time[cust_index] - Globals.customer[cust_index].end_time

        Globals.l_time[cust_index] = Globals.a_time[cust_index] + Globals.customer[cust_index].server_time

        # 在插入新客户后，当前考虑的客户的服务开始时间与原计划服务开始时间的差值。
        # 对于Globals.l_time[cust_index]，假设没有等待时间和延迟时间的情况下，其值为
        # Globals.a_time[cust_index] + Globals.customer[cust_index].server_time
        # 即Globals.l_time[i - 1] + Globals.peer_time[i - 1][cust_index] + Globals.customer[cust_index].server_time
        # 所以到达客户i的时间为
        # Globals.l_time[i - 1] + Globals.peer_time[i - 1][cust_index] + Globals.customer[cust_index].server_time + Globals.peer_time[cust_index][i]
        # 再减去原计划到达客户i的时间，就是因插入客户引起的时间变化
        delta_time = Globals.l_time[cust_index] + Globals.peer_time[cust_index][cust] - Globals.a_time[cust]
        # 如果时间差大于当前客户可以容忍的最大等待时间，则无法插入当前客户
        if delta_time > Globals.max_wait[cust]:
            # print(f"当前客户{cust_index}无法插入到{cust}前")
            continue

        # 插入新客户后路线的总距离变化量。值为正，说明插入后路线变长了；如果为负，则路线变短了。
        delta_dist = -Globals.peer_distance[pre_cust][cust] + Globals.peer_distance[pre_cust][cust_index] + \
                     Globals.peer_distance[cust_index][cust]

        # 这里表示要将客户插入到第i-1和第i个客户之间
        # 表示到达第i个客户的时间
        travel_time = Globals.l_time[cust_index] + Globals.peer_time[cust_index][cust]

        # 如果下一个客户为配送中心
        # if cust == 0 and travel_time > Globals.customer[0].end_time:
        #     print(f"1超过配送中心的最晚服务时间，旅行时间：{travel_time}，最晚服务时间：{Globals.customer[0].end_time}")
        #     continue
        # elif cust != 0 and travel_time > Globals.customer[cust].end_time + Globals.max_delay_time[cust]:
        #     print(
        #         f"1超过当前客户{cust}的最晚服务时间，旅行时间：{travel_time}，最晚服务时间：{Globals.customer[cust].end_time}")
        #     continue

        # 到达第i个客户的时间早于最早服务时间，产生等待时间
        if travel_time < Globals.customer[cust].begin_time:
            wait_time += Globals.customer[cust].begin_time - travel_time
            travel_time = Globals.customer[cust].begin_time
        # 到达第i个客户的时间晚于最晚服务时间，产生延误时间
        if travel_time > Globals.customer[cust].end_time:
            delay_time += travel_time - Globals.customer[cust].end_time
        # 加上第i个客户的服务时间
        travel_time += Globals.customer[cust].server_time

        # flag = False

        # 添加剩余所有客户的时间（旅行时间，延误时间，等待时间）
        for j in range(i, len(route.customers) - 1):
            # print(f"next{route.customers[j + 1]}")
            cur_cust = route.customers[j]
            next_cust = route.customers[j + 1]
            travel_time += Globals.peer_time[cur_cust][next_cust]

            # if cust == 0 and travel_time > Globals.customer[0].end_time:
            #     print(f"2超过配送中心的最晚服务时间，旅行时间：{travel_time}，最晚服务时间：{Globals.customer[0].end_time}")
            #     flag = True
            #     break
            # elif cust != 0 and travel_time > Globals.customer[cust].end_time + Globals.max_delay_time[cust]:
            #     print(
            #         f"2超过当前客户{cust}的最晚服务时间，旅行时间：{travel_time}，最晚服务时间：{Globals.customer[cust].end_time}")
            #     flag = True
            #     break

            if travel_time < Globals.customer[next_cust].begin_time:
                wait_time += Globals.customer[next_cust].begin_time - travel_time
                travel_time = Globals.customer[next_cust].begin_time
            if travel_time > Globals.customer[next_cust].end_time:
                delay_time += travel_time - Globals.customer[next_cust].end_time
            travel_time += Globals.customer[next_cust].server_time

        # print(f"客户{cust_index}插入到{cust}前，时间为：{travel_time}")
        if travel_time > Globals.customer[0].end_time:
            # print(f"客户{cust_index}晚于配送中心时间窗")
            continue
        # if flag:
        #     continue

        # 根据不同的优化目标计算插入客户后的路线改变量
        if r_lambda[1] == 1:
            # 优化目标是最小化总旅行距离
            delta = now_dist + delta_dist
        elif r_lambda[2] == 1:
            # 优化目标是最小化旅行时间
            delta = travel_time
        elif r_lambda[3] == 1:
            # 优化目标是最小化总等待时间
            delta = now_wait + wait_time
        elif r_lambda[4] == 1:
            # 优化目标是最小化总延误时间
            delta = now_delay + delay_time
        else:
            dist = now_dist + delta_dist
            ttime = travel_time
            wait = now_wait + wait_time
            delay = now_delay + delay_time
            # 归一化每个目标函数值，确保了每个目标函数值转换到了同一量级
            r0 = r_lambda[0] * (r_num - Globals.min_num[0]) / (Globals.max_num[0] - Globals.min_num[0] + 1)
            r1 = r_lambda[1] * (dist - Globals.min_num[1]) / (Globals.max_num[1] - Globals.min_num[1] + 1)
            r2 = r_lambda[2] * (ttime - Globals.min_num[2]) / (Globals.max_num[2] - Globals.min_num[2] + 1)
            r3 = r_lambda[3] * (wait - Globals.min_num[3]) / (Globals.max_num[3] - Globals.min_num[3] + 1)
            r4 = r_lambda[4] * (delay - Globals.min_num[4]) / (Globals.max_num[4] - Globals.min_num[4] + 1)
            delta = r0 + r1 + r2 + r3 + r4

        # print(f"当前插入客户{cust}的delta：{delta}，旅行时间：{travel_time}，depot的endtime：{Globals.customer[0].end_time}")
        # 更新最小改变量
        if min_delta > delta:
            # 找到了一个可行的插入位置
            min_delta = delta
            c_index = i
            feasible = True

    result = [feasible, c_index, min_delta]
    # print(result)
    return result


def check_best_pos_for_exchange(route1, cust_index, route2, r_lambda, r_num, dist, now_time, now_wait, now_delay):
    feasible = False
    min_delta = float('inf')
    min_c_pos = 0

    # 创建路线的副本以进行操作，避免修改原始路线

    copy_route = copy.deepcopy(route2)
    get_time(copy_route)
    get_distance(copy_route)

    get_capacity(route1, 0)
    get_capacity(copy_route, 1)

    selected_cust = route1.customers[cust_index]
    selected_next_cust = route1.customers[cust_index + 1]

    for i in range(1, len(copy_route.customers)):
        pre_cust = copy_route.customers[i - 1]
        cur_cust = copy_route.customers[i]
        # 容量检查
        # 原始路线中客户cust_index+1之前的最大载重量减去该点的送货量再加上交换后该点的新送货量
        if (Globals.M_minus[0][cust_index + 1] - Globals.delta_minus[0][cust_index + 1] +
                Globals.delta_minus[1][i] > Globals.max_capacity):
            # print("超重1")
            return [False, 0, 0]
        # 原始路线中客户cust_index之后的最大载重量减去该点原有的取货量加上交换后新的取货量
        if (Globals.M_plus[0][cust_index] - Globals.pi_plus[0][cust_index] +
                Globals.pi_plus[1][i - 1] > Globals.max_capacity):
            # print("超重2")
            return [False, 0, 0]
        # 同上，针对交换的路线
        if (Globals.M_minus[1][i] - Globals.delta_minus[1][i] +
                Globals.delta_minus[0][cust_index + 1] > Globals.max_capacity):
            # print("超重3")
            return [False, 0, 0]
        # 同上，针对交换的路线
        if (Globals.M_plus[1][i - 1] - Globals.pi_plus[1][i - 1] +
                Globals.pi_plus[0][cust_index] > Globals.max_capacity):
            # print("超重4")
            return [False, 0, 0]

        # 检查时间窗约束
        if cur_cust != 0:
            if (Globals.l_time[selected_cust] + Globals.peer_time[selected_cust][cur_cust] >
                    Globals.customer[cur_cust].end_time + Globals.max_delay_time[cur_cust]):
                continue
        else:
            # 检查返回配送中心是否超时
            if (Globals.l_time[selected_cust] + Globals.peer_time[selected_cust][cur_cust] >
                    Globals.customer[cur_cust].end_time):
                continue

        # 检查时间窗约束
        if selected_next_cust != 0:
            if (Globals.l_time[pre_cust] + Globals.peer_time[pre_cust][selected_next_cust] >
                    Globals.customer[selected_next_cust].end_time + Globals.max_delay_time[selected_next_cust]):
                continue
        else:
            if (Globals.l_time[pre_cust] + Globals.peer_time[pre_cust][selected_next_cust] >
                    Globals.customer[selected_next_cust].end_time):
                continue

        # 路线1的时间差
        delta_time_org = Globals.l_time[selected_cust] + Globals.peer_time[selected_cust][cur_cust] - Globals.a_time[
            cur_cust]
        if delta_time_org > Globals.max_wait[cur_cust]:
            continue
        # 路线2的时间差
        delta_time = (Globals.l_time[pre_cust] + Globals.peer_time[pre_cust][selected_next_cust] -
                      Globals.a_time[selected_next_cust])
        if delta_time > Globals.max_wait[selected_next_cust]:
            continue

        # 路线1的距离差
        dist_org = (Globals.b_distance[selected_cust] + Globals.peer_distance[selected_cust][cur_cust] +
                    Globals.a_distance[cur_cust])
        dist_mod = (Globals.b_distance[pre_cust] + Globals.peer_distance[pre_cust][selected_next_cust] +
                    Globals.a_distance[selected_next_cust])

        if dist_org == 0:
            r_num -= 1
        if dist_mod == 0:
            r_num -= 1

        # 计算路线1交换后的时间
        time_1 = Globals.l_time[selected_cust]
        wait_1 = Globals.total_wait[selected_cust]
        delay_1 = Globals.total_delay[selected_cust]
        time_1 += Globals.peer_time[selected_cust][cur_cust]
        if time_1 < Globals.customer[cur_cust].begin_time:
            wait_1 += Globals.customer[cur_cust].begin_time - time_1
            time_1 = Globals.customer[cur_cust].begin_time
        if time_1 > Globals.customer[cur_cust].end_time:
            delay_1 += time_1 - Globals.customer[cur_cust].end_time
        time_1 += Globals.customer[cur_cust].server_time
        for j in range(i + 1, len(copy_route.customers)):
            pre_c = copy_route.customers[j - 1]
            cur_c = copy_route.customers[j]
            time_1 += Globals.peer_time[pre_c][cur_c]
            if time_1 < Globals.customer[cur_c].begin_time:
                wait_1 += Globals.customer[cur_c].begin_time - time_1
                time_1 = Globals.customer[cur_c].begin_time
            if time_1 > Globals.customer[cur_c].end_time:
                delay_1 += time_1 - Globals.customer[cur_c].end_time
            time_1 += Globals.customer[cur_c].server_time

        if time_1 > Globals.customer[0].end_time:
            continue

        # 计算另一条路线的时间
        time_2 = Globals.l_time[pre_cust]
        wait_2 = Globals.total_wait[pre_cust]
        delay_2 = Globals.total_delay[pre_cust]
        time_2 += Globals.peer_time[pre_cust][selected_next_cust]
        if time_2 < Globals.customer[selected_next_cust].begin_time:
            wait_2 += Globals.customer[selected_next_cust].begin_time - time_2
            time_2 = Globals.customer[selected_next_cust].begin_time
        if time_2 > Globals.customer[selected_next_cust].end_time:
            delay_2 += time_2 - Globals.customer[selected_next_cust].end_time
        time_2 += Globals.customer[selected_next_cust].server_time
        for j in range(cust_index + 2, len(route1.customers)):
            pre_c = route1.customers[j - 1]
            cur_c = route1.customers[j]
            time_2 += Globals.peer_time[pre_c][cur_c]
            if time_2 < Globals.customer[cur_c].begin_time:
                wait_2 += Globals.customer[cur_c].begin_time - time_2
                time_2 = Globals.customer[cur_c].begin_time
            if time_2 > Globals.customer[cur_c].end_time:
                delay_2 += time_2 - Globals.customer[cur_c].end_time
            time_2 += Globals.customer[cur_c].server_time

        if time_2 > Globals.customer[0].end_time:
            continue

        if r_lambda[0] == 1:
            delta = r_num
        elif r_lambda[1] == 1:
            delta = dist + dist_mod + dist_org
        elif r_lambda[2] == 1:
            # 选择时间较长的路线
            if time_2 > time_1:
                delta = time_2
            else:
                delta = time_1
        elif r_lambda[3] == 1:
            delta = now_wait + wait_1 + wait_2
        elif r_lambda[4] == 1:
            delta = now_delay + delay_1 + delay_2
        else:
            dist = dist + dist_org + dist_mod
            if time_2 > time_1:
                ttime = time_2
            else:
                ttime = time_1
            wait = now_wait + wait_1 + wait_2
            delay = now_delay + delay_1 + delay_2
            r0 = r_lambda[0] * (r_num - Globals.min_num[0]) / (Globals.max_num[0] - Globals.min_num[0] + 1)
            r1 = r_lambda[1] * (dist - Globals.min_num[1]) / (Globals.max_num[1] - Globals.min_num[1] + 1)
            r2 = r_lambda[2] * (ttime - Globals.min_num[2]) / (Globals.max_num[2] - Globals.min_num[2] + 1)
            r3 = r_lambda[3] * (wait - Globals.min_num[3]) / (Globals.max_num[3] - Globals.min_num[3] + 1)
            r4 = r_lambda[4] * (delay - Globals.min_num[4]) / (Globals.max_num[4] - Globals.min_num[4] + 1)
            delta = r0 + r1 + r2 + r3 + r4

        if min_delta > delta:
            min_delta = delta
            min_c_pos = pre_cust
            feasible = True

    return [feasible, min_c_pos, min_delta]


# 检查路线是否满足时间窗约束
def check_time(route):
    time = 0
    for i in range(len(route.customers) - 1):
        current_customer = route.customers[i]
        next_customer = route.customers[i + 1]

        # 累加到达下一个客户的时间
        time += Globals.peer_time[current_customer][next_customer]
        # print(f"前一个客户{current_customer}到当前客户{next_customer}的时间：{Globals.peer_time[current_customer][next_customer]}")
        # print(f"当前客户{next_customer}的到达时间：{time}")

        # 检查是否超过了下一个客户的最晚服务时间
        if next_customer == 0 and time > Globals.customer[next_customer].end_time:
            # print("check_time结果：返回配送中心超时")
            return False
        if next_customer != 0 and time > Globals.customer[next_customer].end_time + Globals.max_delay_time[
            next_customer]:
            # print("check_time结果：到达下一个客户超时")
            return False

        # 如果提前到达，等待至最早服务时间
        if time < Globals.customer[next_customer].begin_time:
            time = Globals.customer[next_customer].begin_time

        # 加上服务时间，准备前往下一个客户
        time += Globals.customer[next_customer].server_time
        # print(f"当前客户{next_customer}的离开时间：{time}")

    return True


# 比较两个染色体在多个目标上的性能
def is_better(chrome_1, chrome_2):
    better = False
    # print("isbetter")
    # for value in chrome_1.f:
    #     print(f"chrome_1:{value:.6f} ", end="")
    # print()
    # for value in chrome_2.f:
    #     print(f"chrome_2:{value:.6f} ", end="")
    # print()
    for i in range(Globals.FUNC_NUM):
        # 如果chrome_2在至少一个目标上比chrome_1好
        # print(f"chrome_2.f[{i}]-chrome_1.f[{i}]={chrome_2.f[i] - chrome_1.f[i]}")
        if chrome_2.f[i] - chrome_1.f[i] > 0.000001:
            better = True
        #  并且chrome_1在所有目标上都不比chrome_2好
        if chrome_1.f[i] - chrome_2.f[i] > 0.000001:
            return False
    # 则chrome_1非支配chrome_2
    return better


# 比较的是经过转换的目标值
def is_better_box(chrome_1, chrome_2):
    better = False
    for i in range(Globals.FUNC_NUM):
        if chrome_2.box_f[i] - chrome_1.box_f[i] > 0.000001:
            better = True
        if chrome_1.box_f[i] - chrome_2.box_f[i] > 0.000001:
            return False
    return better


# 判断两个染色体在所有目标上的值是否相等
def is_equal(chrome_1, chrome_2):
    for i in range(Globals.FUNC_NUM):
        if abs(chrome_1.f[i] - chrome_2.f[i]) > 0.000001:
            return False
    return True


# 类似于is_equal，但是对比的是box_f数组，即经过某种处理的目标函数值
def is_equal_box(chrome_1, chrome_2):
    for i in range(Globals.FUNC_NUM):
        if abs(chrome_1.box_f[i] - chrome_2.box_f[i]) > 0.000001:
            return False
    return True


# 检查染色体是否在至少一个目标上比当前已知的极值解更好
def is_extreme(chrome):
    for index in range(Globals.FUNC_NUM):
        if Globals.extreme[index].f[index] - chrome.f[index] > 0.000001:
            return True
    return False


# 将原始路线分裂成多条新路线，以确保每条新路线都满足时间窗约束
def split_route(chromosome, route_index):
    temp_route = Globals.Route()  # 创建一个新路线对象
    temp_route.customers.append(0)  # 添加配送中心作为起始点
    previous_cust = 0  # 前一个客户，从配送中心开始
    time = 0  # 到当前客户经历的时间

    # 创建一个副本以避免在迭代时修改列表
    original_customers = list(chromosome.routes[route_index].customers)

    i = 0
    while i < len(chromosome.routes[route_index].customers) - 1:
        now_cust = original_customers[i + 1]  # 当前客户

        time += Globals.peer_time[previous_cust][now_cust]

        # 返回配送中心的时间
        return_time = max(time, Globals.customer[now_cust].begin_time) + Globals.customer[now_cust].server_time + \
                      Globals.peer_time[now_cust][0]

        # 检查是否超出时间窗，需要分裂路线
        if time > Globals.customer[now_cust].end_time + Globals.max_delay_time[now_cust] or return_time > \
                Globals.customer[
                    0].end_time:
            # 分裂路线，完成当前temp_route的创建并重置
            temp_route.customers.append(0)  # 终点为配送中心，结束当前路线
            get_time(temp_route)
            get_distance(temp_route)
            chromosome.routes.append(temp_route)  # 添加到染色体
            temp_route = Globals.Route()
            temp_route.customers.append(0)  # 开始新路线
            previous_cust = 0
            time = 0
        else:
            # 向临时路线添加当前客户
            temp_route.customers.append(now_cust)
            time = max(time, Globals.customer[now_cust].begin_time) + Globals.customer[now_cust].server_time
            previous_cust = now_cust
            i += 1

    # 处理完所有客户后，确保最后一条路线被处理
    get_time(temp_route)
    get_distance(temp_route)
    chromosome.routes.append(temp_route)

    # 从染色体中移除原始路线
    del chromosome.routes[route_index]


def print_chromo_info(chromo):
    get_f(chromo)
    print("f values: ", end="")
    for value in chromo.f:
        print(f"{value:.6f} ", end="")
    # print("\nbox_f values: ", end="")
    # for value in chromo.box_f:
    #     print(f"{value} ", end="")
    print()


def output(f):
    Globals.EP.sort()
    for i, chromo in enumerate(Globals.EP):
        # 假设 chromo.f 是包含目标函数值的列表
        print(" ".join([f"{val:.6f}" for val in chromo.f]), file=f)


def check_EP():
    for chromosome in Globals.EP:
        used = [False] * (Globals.customer_num + 1)  # 初始化标记所有客户未被服务
        # 遍历所有路线
        for route in chromosome.routes:
            d_capacity = 0  # 初始化总送货量
            t_time = 0  # 旅行时间
            w_time = 0  # 等待时间

            # 累加送货量，检查是否超过最大容量
            for i in range(1, len(route.customers) - 1):
                current_cust = route.customers[i]
                d_capacity += Globals.customer[current_cust].delivery_demand
                if d_capacity > Globals.max_capacity:
                    # print("delivery capacity false!")
                    return False

            # 检查送货后的取货操作是否导致超过最大容量
            for i in range(1, len(route.customers) - 1):
                current_cust = route.customers[i]
                d_capacity = d_capacity - Globals.customer[current_cust].delivery_demand + Globals.customer[
                    current_cust].pick_up_demand
                if d_capacity > Globals.max_capacity:
                    # print(f"路线:{' -> '.join(map(str, route.customers))}")
                    # print("pickup capacity false!", d_capacity)
                    return False

            # 计算行驶时间，检查是否违反时间窗约束
            for i in range(len(route.customers) - 1):
                current_cust = route.customers[i]
                next_cust = route.customers[i + 1]
                t_time += Globals.peer_time[current_cust][next_cust]

                if next_cust != 0:
                    if t_time > Globals.customer[next_cust].end_time + Globals.max_delay_time[next_cust]:
                        # print(f"路线:{' -> '.join(map(str, route.customers))} 客户：{current_cust}")
                        # print("time window violation!")
                        return False
                else:  # 返回配送中心
                    if t_time > Globals.customer[0].end_time:
                        # print(f"路线:{' -> '.join(map(str, route.customers))}")
                        # print("depot end time false!")
                        return False
                if t_time < Globals.customer[next_cust].begin_time:
                    w_time = Globals.customer[next_cust].begin_time - t_time
                else:
                    w_time = 0
                t_time += w_time + Globals.customer[next_cust].server_time

                used[current_cust] = True  # 标记当前客户已被服务

        # 检查是否所有客户都已被服务
        if sum(used[1:]) != Globals.customer_num:  # 排除配送中心的索引0
            # print("Not all customers are served!")
            return False

    return True


def output_best(f):
    Globals.total_best.sort()
    for chromo in Globals.total_best:
        # 假设 chromo.f 是包含目标函数值的列表
        print(" ".join([f"{val:.6f}" for val in chromo.f]), file=f)


def print_extreme_info():
    print("打印极端数组extreme")
    for i in range(Globals.FUNC_NUM):
        print(f"{i + 1}:{Globals.extreme[i].f}")
    print()


def out_N():
    out_file = "result.txt"
    with open(out_file, "w") as file:
        for i in range(Globals.N):
            chmosome = Globals.chromosome[i]
            print(" ".join([f"{val:.6f}" for val in chmosome.f]), file=file)
